{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distinct Numbers in Each Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distinctNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每个子数组的数字种类数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>与一个整数 <code>k</code>，请你构造一个长度 <code>n-k+1</code> 的数组 <code>ans</code>，这个数组第<code>i</code>个元素 <code>ans[i]</code> 是每个长度为k的子数组 <code>nums[i:i+k-1] = [nums[i], nums[i+1], ..., nums[i+k-1]]</code>中数字的种类数。</p>\n",
    "\n",
    "<p>返回这个数组 <code>ans</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3,2,2,1,3], k = 3\n",
    "<strong>输出:</strong> [3,2,2,2,3]\n",
    "<b>解释</b>：每个子数组的数字种类计算方法如下：\n",
    "- nums[0:2] = [1,2,3] 所以 ans[0] = 3\n",
    "- nums[1:3] = [2,3,2] 所以 ans[1] = 2\n",
    "- nums[2:4] = [3,2,2] 所以 ans[2] = 2\n",
    "- nums[3:5] = [2,2,1] 所以 ans[3] = 2\n",
    "- nums[4:6] = [2,1,3] 所以 ans[4] = 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,1,1,1,2,3,4], k = 4\n",
    "<strong>输出:</strong> [1,2,3,4]\n",
    "<strong>解释: </strong>每个子数组的数字种类计算方法如下：\n",
    "- nums[0:3] = [1,1,1,1] 所以 ans[0] = 1\n",
    "- nums[1:4] = [1,1,1,2] 所以 ans[1] = 2\n",
    "- nums[2:5] = [1,1,2,3] 所以 ans[2] = 3\n",
    "- nums[3:6] = [1,2,3,4] 所以 ans[3] = 4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distinct-numbers-in-each-subarray](https://leetcode.cn/problems/distinct-numbers-in-each-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distinct-numbers-in-each-subarray](https://leetcode.cn/problems/distinct-numbers-in-each-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2,2,1,3]\\n3', '[1,1,1,1,2,3,4]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 如果nums为空或者k为0, 直接返回空列表\n",
    "        if not nums or k == 0:\n",
    "            return []\n",
    "\n",
    "        # 使用字典记录当前窗口内数字的出现次数\n",
    "        counter = defaultdict(int)\n",
    "        result = []\n",
    "\n",
    "        # 初始化窗口和counter字典\n",
    "        for i in range(k):\n",
    "            counter[nums[i]] += 1\n",
    "        result.append(len(counter))\n",
    "\n",
    "        # 滑动窗口，每次移动一步\n",
    "        for i in range(k, len(nums)):\n",
    "            # 增加新元素的计数\n",
    "            counter[nums[i]] += 1\n",
    "            # 减少最左边元素的计数\n",
    "            counter[nums[i-k]] -= 1\n",
    "            # 如果某个数字的计数变为0，从字典中移除它\n",
    "            if counter[nums[i-k]] == 0:\n",
    "                del counter[nums[i-k]]\n",
    "            # 更新结果\n",
    "            result.append(len(counter))\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums[:k])\n",
    "        ans = [len(cnt)]\n",
    "        for i in range(k, n):\n",
    "            x, y = nums[i], nums[i-k]\n",
    "            cnt[x] += 1\n",
    "            cnt[y] -= 1\n",
    "            if cnt[y] == 0:\n",
    "                del cnt[y]\n",
    "            ans.append(len(cnt))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        d, l, res = defaultdict(int), 0, []\n",
    "        for r, n in enumerate(nums):\n",
    "            d[n] += 1\n",
    "            if r - l + 1 == k:\n",
    "                res.append(len(d))\n",
    "                d[nums[l]] -= 1\n",
    "                if d[nums[l]] == 0:\n",
    "                    d.pop(nums[l])\n",
    "                l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        mp = collections.defaultdict(int)\n",
    "        for i in range(k):\n",
    "            mp[nums[i]] +=1\n",
    "        ans = [len(mp)]\n",
    "        for i in range(k, len(nums)):\n",
    "            f, l = nums[i-k], nums[i]\n",
    "            if mp[f] == 1:\n",
    "                del mp[f]\n",
    "            else:\n",
    "                mp[f] -=1\n",
    "            mp[l] +=1\n",
    "            ans.append(len(mp))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        ret = []\n",
    "        d = Counter(nums[0: k]) # number -> occurrence\n",
    "        key_num = len(d.keys())\n",
    "        ret.append(key_num)\n",
    "        for i in range(1, len(nums) - k + 1):\n",
    "            out_num = nums[i - 1]\n",
    "            d[out_num] -= 1\n",
    "            in_num = nums[i + k - 1]\n",
    "            if in_num in d:\n",
    "                d[in_num] += 1\n",
    "            else:\n",
    "                d[in_num] = 1\n",
    "                key_num += 1\n",
    "            if d[out_num] == 0:\n",
    "                d.pop(out_num)\n",
    "                key_num -= 1\n",
    "            ret.append(key_num)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        ret = []\n",
    "        d = Counter(nums[0: k]) # number -> occurrence\n",
    "        ret.append(len(d.keys()))\n",
    "        for i in range(1, len(nums) - k + 1):\n",
    "            out_num = nums[i - 1]\n",
    "            d[out_num] -= 1\n",
    "            in_num = nums[i + k - 1]\n",
    "            d[in_num] = d[in_num] + 1 if in_num in d else 1\n",
    "            if d[out_num] == 0:\n",
    "                d.pop(out_num)\n",
    "            ret.append(len(d.keys()))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums[:k])\n",
    "        ans = [len(cnt)]\n",
    "        for i in range(1, n - k + 1):\n",
    "            cnt[nums[i - 1]] -= 1\n",
    "            cnt[nums[i + k - 1]] += 1\n",
    "            if cnt[nums[i - 1]] == 0:\n",
    "                del cnt[nums[i - 1]]\n",
    "            ans.append(len(cnt))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        left=0\n",
    "        right=k-1\n",
    "\n",
    "\n",
    "        w_dic={}\n",
    "        result=[]\n",
    "        for i in range(k):\n",
    "            if w_dic.get(nums[i])==None:\n",
    "                w_dic[nums[i]]=1\n",
    "            else:\n",
    "                w_dic[nums[i]]+=1\n",
    "\n",
    "        while right<=len(nums)-1:\n",
    "            result.append(len(w_dic.keys()))\n",
    "            w_dic[nums[left]]-=1\n",
    "            if w_dic[nums[left]]==0:\n",
    "                del w_dic[nums[left]]\n",
    "            left+=1\n",
    "            right+=1\n",
    "            if right>len(nums)-1:\n",
    "                break\n",
    "            if w_dic.get(nums[right])==None:\n",
    "                w_dic[nums[right]]=1\n",
    "            else:\n",
    "                w_dic[nums[right]]+=1\n",
    "        return result\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 滑动窗口\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        mp = collections.defaultdict(int)\n",
    "        for i in range(k):\n",
    "            mp[nums[i]] +=1\n",
    "\n",
    "        ans = [len(mp)]\n",
    "        for i in range(k, len(nums)):\n",
    "            f, l = nums[i-k], nums[i]\n",
    "            if mp[f] == 1:\n",
    "                del mp[f]\n",
    "            else:\n",
    "                mp[f] -= 1\n",
    "\n",
    "            mp[l] += 1\n",
    "            ans.append(len(mp))\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        window = defaultdict(lambda: 0)\n",
    "        # 统计前k个 right = [0, 1, .., k - 1]\n",
    "        for right, c in enumerate(nums[:k]):\n",
    "            window[c] += 1\n",
    "        cnt = len(window.keys())\n",
    "        res.append(cnt)\n",
    "        # right = k\n",
    "        for i, c in enumerate(nums[k:]):\n",
    "            window[c] += 1\n",
    "            if window[c] == 1:\n",
    "                cnt += 1\n",
    "            d = nums[i]\n",
    "            window[d] -= 1\n",
    "            if window[d] == 0:\n",
    "                cnt -= 1\n",
    "            \n",
    "            # 保存结果\n",
    "            res.append(cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans=[]\n",
    "        map=Counter(nums[:k])\n",
    "        ans.append(len(map))\n",
    "        left=0\n",
    "        right=k\n",
    "        while right<len(nums):\n",
    "            map[nums[right]]+=1\n",
    "            right+=1\n",
    "            map[nums[left]]-=1\n",
    "            if not map[nums[left]]:\n",
    "                map.pop(nums[left])\n",
    "            left+=1\n",
    "            ans.append(len(map))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        d=defaultdict(int)\n",
    "        res=0\n",
    "        ans=[]\n",
    "        for i in range(k):\n",
    "            d[nums[i]]+=1\n",
    "            if d[nums[i]]==1:\n",
    "                res+=1\n",
    "        ans.append(res)\n",
    "        for i in range(k,n):\n",
    "            d[nums[i]]+=1\n",
    "            if d[nums[i]]==1:\n",
    "                res+=1\n",
    "            d[nums[i-k]]-=1\n",
    "            if d[nums[i-k]]==0:\n",
    "                res-=1\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        dq = deque(nums[:k])\n",
    "        cnts = Counter(nums[:k])\n",
    "        ans.append(len(cnts))\n",
    "        for x in nums[k:]:\n",
    "            y = dq.popleft()\n",
    "            dq.append(x)\n",
    "            cnts[x] += 1\n",
    "            cnts[y] -= 1\n",
    "            if cnts[y] == 0: del cnts[y]\n",
    "            ans.append(len(cnts))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
